Array.prototype.filter = function (callback,thisArg){
    // console.log(callback);
    
    const res = []
    if(this==null){
        throw TypeError('this is null or undefined!')
    }

    if(typeof callback!== 'function'){
        throw TypeError('the first parameter must be a function!')
    }
    let array = Object(this),T;
    const len = array.length>>>0
    // console.log(len);
    if(arguments.length>1){
        T=thisArg
    }
    let k=0,kVal;
    while(k<len){
        if(k in array){
            // console.log(k);
            kVal = array[k]
            if(callback.call(T,kVal,k,array)){
                res.push(kVal)
            }
        }
        k++
    }
    return res
}

// const arr = [1,2,3,4,5,6]
// console.log(arr.filter(item=>item>3));

function quickSort(arr){
    if(arr.length<2){
        return arr
    }
    const pivot = arr[Math.floor(Math.random()*arr.length)]
    const leftArr = arr.filter(item=>item<pivot)
    const rightArr = arr.filter(item=>item>pivot)
    return [...quickSort(leftArr),pivot,...quickSort(rightArr)]
}

const arr = [5,3,1,7,8,9]
console.log(quickSort(arr));